package hot_100;

import java.util.HashMap;

public class 最小覆盖子串 {
    public static void main(String[] args) {
        String s = minWindow("ADOBECODEBANC", "ABC");
        System.out.println(s);
    }

    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] tt = t.toCharArray();
        char[] ss = s.toCharArray();
        int cnt = 0;
        for (char c : tt) {
            Integer merge = map.merge(c, 1, Integer::sum);
            if (merge == 1)
                cnt++;
        }
        int ansl = -1, ansr = s.length() + 1;
        int st = 0;
        for (int ed = 0; ed < ss.length; ed++) {
            Integer merge = map.merge(ss[ed], -1, Integer::sum);
            if (merge == 0)
                cnt--;
            while (cnt == 0) {
                int len = ed - st + 1;
                if (len < ansr - ansl + 1) {
                    ansl = st;
                    ansr = ed;
                }
                Integer mg = map.merge(ss[st], 1, Integer::sum);
                if (mg == 1) {
                    cnt++;
                }
                st++;
            }
        }
        if (ansl == -1)
            return "";
        return s.substring(ansl, ansr + 1);
    }
}
